package class07_加强堆.test;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * 加强堆
 */
public class HeapGreater<T> {
    private ArrayList<T> heap;
    private int heapSize;
    //反向索引
    private HashMap<T,Integer> indexMap;
    private Comparator<? super T> comp;
    public HeapGreater(Comparator<T> c){
        heap = new ArrayList<>();
        heapSize = 0;
        indexMap = new HashMap<>();
        this.comp = c;
    }
    public boolean isEmpty(){
        return heapSize == 0;
    }
    public int size(){
        return heapSize;
    }
    public boolean contains(T obj){
        return indexMap.containsKey(obj);
    }
    public T peek(){
        return heap.get(0);
    }
    public void push(T obj){
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }
    public T pop(){
        T ans = heap.get(0);
        swap(heap, 0, --heapSize);
        heap.remove(heapSize);
        indexMap.remove(ans);
        heapify(0);
        return ans;
    }
    public void remove(T obj){
        T t = heap.get(--heapSize);
        int index = indexMap.get(obj);
        heap.remove(heapSize);
        indexMap.remove(obj);
        if(t != obj){
            heap.set(index, t);
            indexMap.put(obj, index);
            resign(obj);
        }
    }
    public List<T> getAllElements(){
        List<T> ans = new ArrayList<>();
        for (int i = 0; i < heap.size(); i++) {
            ans.add(heap.get(i));
        }
        return ans;
    }
    public void resign(T obj){
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    private void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize){
            int largest = left + 1 < heapSize && comp.compare(heap.get(left), heap.get(left + 1)) < 0 ? left + 1 : left;
            largest = comp.compare(heap.get(index), heap.get(largest)) < 0 ? largest : left;
            if(largest == index){
                break;
            }
            swap(heap, index, largest);
            index = largest;
            left = index * 2 + 1;
        }

    }

    private void heapInsert(int index) {
        while (comp.compare(heap.get((index - 1) / 2), heap.get(index)) < 0){
            swap(heap, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(ArrayList<T> heap, int a, int b) {
        T temp = heap.get(a);
        T temp2 = heap.get(b);
        indexMap.put(temp,b);
        indexMap.put(temp2,a);
        heap.set(b,temp);
        heap.set(a,temp2);
    }
}
